package com.hutu;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class OpenLock {

    /**
     * 开锁问题
     */
    public static int openLock(String[] deadends, String target) {

        HashSet<String> visited = new HashSet<>(Arrays.asList(deadends));
        Queue<String> q = new LinkedList<>();
        q.offer("0000");
        if (visited.contains("0000")){
            return -1;
        }
        visited.add("0000");
        int res = 0;
        while (!q.isEmpty()){
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                String cur = q.poll();
                if (cur.equals(target)){return res;}
                for (int j = 0; j < 4; j++) {
                    String temp = plusOne(cur, j);
                    if (!visited.contains(temp)){
                        q.offer(temp);
                        visited.add(temp);
                    }
                    temp = minusOne(cur, j);
                    if (!visited.contains(temp)){
                        q.offer(temp);
                        visited.add(temp);
                    }
                }
            }
            res++;
        }
        return -1;
    }
    public static String plusOne(String s,int j){
        char[] chars = s.toCharArray();
        if(chars[j] == '9'){
            chars[j] =  '0';
        }else {
            chars[j] +=1;

        }
        return new String(chars);
    }
    public static String minusOne(String s,int j){
        char[] chars = s.toCharArray();
        if(chars[j] == '0'){
            chars[j] = '9';
        }else {
            chars[j] -=1;

        }
        return new String(chars);
    }
}
